package com.LeeCode;

import java.util.Arrays;

/**
 * 收集连续 K 个袋子可以获得的最多硬币数量
 */

public class Code3413 {
    public static void main(String[] args) {
        int[][] coins = {
                {8, 10, 1},
                {1, 3, 2},
                {5, 6, 4}
        };
        int k = 4;

        System.out.println(new Code3413().maximumCoins(coins, k));
    }

    public long maximumCoins(int[][] coins, int k) {
        Arrays.sort(coins, (a, b) -> a[0] - b[0]);
        long ans = 0;
        ans = aux(coins, k);

        // 反转数组
        for (int i = 0, j = coins.length - 1; i < j; i++, j--) {
            int[] tmp = coins[i];
            coins[i] = coins[j];
            coins[j] = tmp;
        }
        // 反转每个区间
        for (int[] t : coins) {
            int tmp = t[0];
            t[0] = -t[1];
            t[1] = -tmp;
        }

        ans = Math.max(ans, aux(coins, k));

        return ans;
    }

    private long aux(int[][] coins, int k) {
        long ans = 0, cover = 0;
        int left = 0;

        for (int[] coin : coins) {
            int cl = coin[0], cr = coin[1];
            cover += (long) (cr - cl + 1) * coin[2];

            while (cr - coins[left][1] + 1 > k) {
                cover -= (long) (coins[left][1] - coins[left][0] + 1) * coins[left][2];
                left++;
            }

            long uncover = Math.max((long) (cr - k + 1 - coins[left][0]) * coins[left][2], 0);

            ans = Math.max(ans, cover - uncover);

        }
        return ans;
    }
}
